//
// Created by shenbin on 2022/4/24.
// https://leetcode-cn.com/problems/degree-of-an-array/
//

#ifndef ALGORITHM_TRAINNING_W02_H02_LC697_H
#define ALGORITHM_TRAINNING_W02_H02_LC697_H

#include <unordered_map>
#include <vector>

using namespace std;

class LeetCode697 {
public:
    /**
     * 思路：
     * 1. 用hash表按照数组元素分组计数，数组最大的度
     * 2. 计数过程中，记录每个元素的起始位置
     * 3. 当元素的度与数组最大的度相同，最小子数组即为起始位置均为元素的数组
     * 注意：
     * 1. 取最大值时，比较的初始值取最小，取最小值时，比较的初始值取最大
     * 2. int类型为4个字节32位，1个16进制数为4位，2个16进制为8位（1个字节）
     *   F=1111， 7=01111，
     *   最小值：0xffffffff，最大值：0x7fffffff
     * @param nums
     * @return
     */
    int findShortestSubArray(vector<int> &nums) {
        int degree = 0xffffffff, minLength = 0x7fffffff;
        for (int i = 0; i < nums.size(); i++) {
            if (h.find(nums[i]) != h.end()) {
                h[nums[i]][0]++;
                h[nums[i]][2] = i;
            } else {
                h[nums[i]] = {1, i, i};
            }
            degree = max(h[nums[i]][0], degree);
        }
        for (pair<int, vector<int>> num: h) {
            if (num.second[0] == degree) {
                min(minLength, num.second[2] - num.second[1] + 1);
            }
        }
        return minLength;
    }

private:
    unordered_map<int, vector<int>> h;

};

#endif //ALGORITHM_TRAINNING_W02_H02_LC697_H
